package course;

public class SpecialFunction {
    
    /**
     * 根据给定规律计算 f(n)
     * 规律：
     * - 如果 n 是 2 的幂，返回 0
     * - 否则，提取奇数部分 m，分析其质因数结构：
     *   - m = p^k        -> 返回 k
     *   - m = p * q      -> 返回 3
     *   - m = p^2 * q    -> 返回 5
     *   - m = p^4        -> 返回 4
     */
    public static int f(int n) {
        // 1. 如果是 2 的幂：n > 0 且 (n & (n-1)) == 0
        if (n > 0 && (n & (n - 1)) == 0) {
            return 0;
        }
        
        // 2. 去掉因子 2，得到奇数部分 m
        int m = n;
        while (m % 2 == 0) {
            m /= 2;
        }
        
        if (m == 1) {
            return 0; // 已经是 2 的幂，前面应已处理，但保险
        }
        
        // 3. 分解 m 的质因数
        int temp = m;
        int first_p = 0;       // 第一个质因子（实际未使用）
        int first_exp = 0;     // 第一个质因子的指数
        int second_p = 0;      // 第二个质因子（未使用）
        int second_exp = 0;    // 第二个质因子的指数
        int factor_count = 0;  // 质因子种类数
        
        // 先试因子 3, 5, 7, ... 直到 sqrt(temp)
        int p = 3;
        while (p * p <= temp) {
            if (temp % p == 0) {
                int count = 0;
                while (temp % p == 0) {
                    count++;
                    temp /= p;
                }
                if (factor_count == 0) {
                    first_exp = count;
                } else if (factor_count == 1) {
                    second_exp = count;
                }
                factor_count++;
            }
            p += 2;
        }
        
        // 如果 temp > 1，说明还有一个质因子
        if (temp > 1) {
            if (factor_count == 0) {
                first_exp = 1;
            } else if (factor_count == 1) {
                second_exp = 1;
            }
            factor_count++;
        }
        
        // 4. 根据质因数情况返回结果
        if (factor_count == 1) {
            return first_exp;
        } else if (factor_count == 2) {
            if ((first_exp == 2 && second_exp == 1) || (first_exp == 1 && second_exp == 2)) {
                return 5;
            } else {
                return 3;
            }
        } else {
            return 3; // 三个或以上质因子
        }
    }
    // 测试方法
    public static void main(String[] args) {
        System.out.println("n\tf(n)");
        System.out.println("--------------");
        for (int i = 1; i <= 100; i++) {
            System.out.printf("%d\t%d%n", i, f(i));
        }
    }
}
